/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica1.practica;

import Practica1.util.Edge;
import Practica1.util.Euler;
import Practica1.util.Graph;
import Practica1.util.Vertex;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *
 * @author miguel
 */
public class MyEuler implements Euler {

    /**
     * Si la gráfica no es dirigida y es conexa, verifica que sea una gráfica
     * euleriana <b>Teorema: </b> Sea G un grafo no dirigido y conexo:<br> 1.- G
     * es euleriano si y sólo si no tiene vertices de grado impar<br> 2.- G
     * admite un camino euleriano si y sólo si tiene exactamente dos veértices
     * de grado impar.
     *
     * @param graph gráfica a verificar si es euleriana.
     * @return Verdadero si es euleriana o admite un ciclo euleriano. Falso en
     * otro caso.
     */
    private boolean isEulerianNotDirected(Graph graph) {
        int numVertexImpar = 0;

        for (Vertex v : (List<Vertex>) graph.getVertexList()) {
            if (v.grade() % 2 == 1) {
                numVertexImpar++;
            }
        }
        if (numVertexImpar == 0 || numVertexImpar == 2) {
            return true;
        }
        return false;
    }

    /**
     * Si la gráfica es dirigida entonces debe cumplir el siguiente teorema<br>
     * <b>Teorema: </b><i> Un grafo dirigido es euleriano si es conexo y para
     * cada v en V, <b>v.ingrado = v.exgrado</b></i>
     *
     * @param graph
     * @return
     */
    private boolean isEulerianDirected(Graph graph) {

        List<Vertex> listVertex = graph.getVertexList();
        int[] arrayVertexIngrado = new int[listVertex.size()];
        int[] arrayVertexExgrado = new int[listVertex.size()];
        List<Edge> listEdges = graph.getEdgesList();
        int i = 0;
        for (Vertex v : listVertex) {
            for (Edge e : listEdges) {
                if (e.getTarget().equals(v)) {
                    arrayVertexIngrado[i]++;
                }
                if (e.getSource().equals(v)) {
                    arrayVertexExgrado[i]++;
                }
            }
            i++;
        }

        for (int j = 0; j < arrayVertexExgrado.length; j++) {
            if (arrayVertexIngrado[j] != arrayVertexExgrado[j]) {
                return false;
            }
        }
        return true;
    }

    @Override
    public List<Edge> getDirectedCircuit(Graph graph, int vertex) {
        if (isEulerianDirected(graph)) {
            Vertex v = graph.getVertex(vertex);
            if (!(v.getNeighboursList().size() > 0)) {
                return new ArrayList<>();
            }
            List<MyEdge> edges = graph.getEdgesList();
            Stack<MyEdge> edgesVisited = new Stack<>();
            MyEdge e = (MyEdge) graph.getEdge(v, v.getNeighbour(0));
            edges.remove(e);
            edgesVisited.push(e);
            e.setVisited(true);
            Vertex v4 = null;
            while ((e != null && !e.getTarget().equals(v)) || !edges.isEmpty()) {
                Vertex v2 = e.getTarget();
                MyEdge e2 = null;
                for (Vertex v3 : (List<Vertex>) v2.getNeighboursList()) {
                    if (v4 != null && !v3.equals(v4)) {
                        e2 = (MyEdge) graph.getEdge(v2, v3);
                        if (e2 != null) {
                            e2.setVisited(true);
                            edges.remove(e2);
                            edgesVisited.push(e2);
                            break;
                        }
                    } else if (v4 == null) {
                        e2 = (MyEdge) graph.getEdge(v2, v3);
                        if (e2 != null) {
                            e2.setVisited(true);
                            edges.remove(e2);
                            edgesVisited.push(e2);
                            break;
                        }
                    }
                }
                if (!edges.isEmpty()) {
                    if (e2 != null) {
                        e = e2;
                        v4 = null;
                    } else {
                        e.setVisited(false);
                        edges.add(e);
                        e = edgesVisited.pop();
                        v4 = e.getTarget();
                    }
                }else{
                    break;
                }

            }
            return (List) edgesVisited;
        }
        return new ArrayList<>();

    }

    @Override
    public List<Edge> getCircuit(Graph graph, int vertex) {
        if (isEulerianNotDirected(graph)) {
            Vertex v = graph.getVertex(vertex);
            if (!(v.getNeighboursList().size() > 0)) {
                return new ArrayList<>();
            }
            List<MyEdge> edges = graph.getEdgesList();
            Stack<MyEdge> edgesVisited = new Stack<>();
            MyEdge e = (MyEdge) graph.getEdge(v, v.getNeighbour(0));
            edges.remove(e);
            edgesVisited.push(e);
            e.setVisited(true);
            Vertex v4 = null;
            while ((e != null && !e.getTarget().equals(v)) || !edges.isEmpty()) {
                Vertex v2 = e.getTarget();
                MyEdge e2 = null;
                for (Vertex v3 : (List<Vertex>) v2.getNeighboursList()) {
                    if (v4 != null && !v3.equals(v4)) {
                        e2 = (MyEdge) graph.getEdge(v2, v3);
                        if (e2 != null) {
                            e2.setVisited(true);
                            edges.remove(e2);
                            edgesVisited.push(e2);
                            break;
                        }
                    } else if (v4 == null) {
                        e2 = (MyEdge) graph.getEdge(v2, v3);
                        if (e2 != null) {
                            e2.setVisited(true);
                            edges.remove(e2);
                            edgesVisited.push(e2);
                            break;
                        }
                    }
                }
                if (!edges.isEmpty()) {
                    if (e2 != null) {
                        e = e2;
                        v4 = null;
                    } else {
                        e.setVisited(false);
                        edges.add(e);
                        e = edgesVisited.pop();
                        v4 = e.getTarget();
                    }

                }else{
                    break;
                }
            }
            return (List) edgesVisited;
        }
        return new ArrayList<>();

    }
}
